package com.zk.algorithm;

/**
 * 并查集
 *
 * Disjoint-set data structure
 * union-find data structure
 *
 * https://en.wikipedia.org/wiki/Disjoint-set_data_structure
 *
 * Union by rank always attaches the shorter tree to the root of the taller tree.
 * Thus, the resulting tree is no taller than the originals unless they were of equal height,
 * in which case the resulting tree is taller by one node.
 */
public class UnionFind {

    private int[] p;
    // shorter 树依附在 taller 树上
    private int[] rank;
    private int num;

    public UnionFind(int num) {
        this.p = new int[num];
        for (int i=0; i<num; i++) {
            this.p[i] = i;
        }

        this.rank = new int[num];
        this.num = num;
    }

    public int find(int index) {
        if (p[index] == index) {
            return index;
        }

        return find(p[index]);
    }

    /**
     * Union by rank 算法
     * (Union by size) 算法
     *
     * - 每个元素关联了一个 rank
     * - 不相同？设置为较大的那个
     * - 相同？rank + 1
     *
     * @param i
     * @param j
     */
    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);

        if (rootI == rootJ) {
            return;
        }

        // if two sets are unioned and have different ranks,
        // the resulting set's rank is the larger of the two (两个之中较大的那个)
        if (rank[rootI] > rank[rootJ]) {
            p[rootJ] = rootI;
        } else {
            p[rootI] = rootJ;
        }

        //  If two sets are unioned and have the same rank,
        //  the resulting set's rank is one larger (大一个)
        if (rank[rootI] == rank[rootJ]) {
            rank[rootJ]++;
        }

        num--;
    }

    public int size() {
        return num;
    }

}
